package sorttest;

import static java.util.Collections.swap;

public class sort1 {


    //希尔排序
    public static void shellSort(int[] arr) {
        int n = arr.length;
        int gap = n / 2;
        while (gap > 0) {
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j = i;
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
            gap /= 2;
        }
    }


    // 快速排序
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high);
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
    }

    //三数取中法
public static void quick(int []arr,int start,int end){
        if(start>=end){//为什么这个时候数组只有一个元素？
            return;
        }
        int mid=getMid(arr,start,end);
        swap(arr,start,mid);
        int pivot = partition(arr, start, end);
        quickSort(arr, start, pivot - 1);
        quickSort(arr, pivot + 1, end);

}
public static int getMid(int []arr,int start,int end){
        int mid=(start+end)/2;
        if(arr[start]>arr[mid]){
            swap(arr,start,mid);
        }
        if(arr[start]>arr[end]){
            swap(arr,start,end);
        }
        if(arr[mid]>arr[end]){
            swap(arr,mid,end);
        }
        return mid;
}
























    // 快速排序的分区函数
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        int i = low;
        int j = high;
        while (i < j) {
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            arr[i] = arr[j];
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = pivot;
        return i;
    }

    //快速排序挖坑法
    public static int paratition(int[] array, int left, int right) {
        int tmp = array[left];
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }


    //快速排序Hoare法
    public static int paratitionHoare(int[] array, int left, int right) {
        int tmp = array[left];
        int tmpleft = array[left];
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            while (left < right && array[left] <= tmp) {
                left++;
            }
            swap(array, left, right);
        }
        swap(array, left, tmpleft);
        return left;
    }

    private static void swap(int[] array, int left, int right) {
        int tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }
    //快速排序非递归
    public static void quickSortNoRecur(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = paratition(array, left, right);
        quickSortNoRecur(array, left, pivot - 1);
        quickSortNoRecur(array, pivot + 1, right);
    }















    public class MergeSort {
        public static void mergeSort(int[] arr, int left, int right) {
            if (left >= right) {
                return;
            }
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
        public static void merge(int[] arr, int left, int mid, int right) {
            int[] temp = new int[right - left + 1];
            int i = left, j = mid + 1, k = 0;
            while (i <= mid && j <= right) {
                if (arr[i] <= arr[j]) {
                    temp[k++] = arr[i++];
                } else {
                    temp[k++] = arr[j++];
                }
            }
            while (i <= mid) {
                temp[k++] = arr[i++];
            }
            while (j <= right) {
                temp[k++] = arr[j++];
            }
            for (int p = 0; p < temp.length; p++) {
                arr[left + p] = temp[p];
            }
        }
        public static void main(String[] args) {
            int[] arr = {5, 2, 8, 3, 6, 1, 7, 9, 4};
            mergeSort(arr, 0, arr.length - 1);
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
        }
    }

}


